class Solution
{
public:
    // 1. 预处理回文子串
    // 2. 用dfs找分割方法
    enum
    {
        N = 2010
    };
    int dp[N][N];
    int f[N];
    void dp_init(const string &s)
    {
        for (int len = 1; len <= s.size(); ++len)
        {
            for (int left = 0; left + len - 1 < s.size(); ++left)
            {
                int right = left + len - 1;
                if (left == right)
                    dp[left][right] = true;
                else if (s[left] == s[right])
                {
                    if (left + 1 == right)
                        dp[left][right] = true;
                    else
                        dp[left][right] = dp[left + 1][right - 1];
                }
            }
        }
    }

    int minCut(string s)
    {
        // 只要能快速缩减到一个比较小的数照理是不会超时的
        // 但是有一个致命的命题是如果每个字母都不一样永远没办法缩减
        // 需要想别的办法，再用一次dp不就行了吗！千万别思维定势了！！
        dp_init(s);
        int min_time = INT_MAX;
        f[0] = -1;
        // f[i] 表示将前i个数分割成一个个回文串需要的最小次数
        for (int i = 2; i <= s.size(); ++i)
        {
            int min_st = INT_MAX;
            for (int j = i; j > 0; --j)
            {
                // if(i == 2 && j == 1) cout << dp[0][1] << "f[0]" << f[0] << endl;
                if (dp[j - 1][i - 1])
                    min_st = min(min_st, f[j - 1] + 1);
                // if(i == 2 && j == 1) cout << min_st << endl;
            }
            f[i] = min_st;
            // cout << i << ' ' << f[i] << endl;
        }
        return f[s.size()];
    }
};